<!DOCTYPE html>
<html  lang="zh">
<head>
    <meta charset="utf-8" />

<meta name="generator" content="Hexo 3.8.0" />

<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1" />

<title>《大话数据结构》一 - OBJC.VIP</title>


    <meta name="description" content="第1章 数据结构绪论">
<meta name="keywords" content="学习笔记">
<meta property="og:type" content="article">
<meta property="og:title" content="《大话数据结构》一">
<meta property="og:url" content="https://objcvip.github.io/DataStructurePart1/index.html">
<meta property="og:site_name" content="OBJC.VIP">
<meta property="og:description" content="第1章 数据结构绪论">
<meta property="og:locale" content="zh-CN">
<meta property="og:image" content="https://objcvip.github.io/images/og_image.png">
<meta property="og:updated_time" content="2019-09-04T06:58:05.423Z">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="《大话数据结构》一">
<meta name="twitter:description" content="第1章 数据结构绪论">
<meta name="twitter:image" content="https://objcvip.github.io/images/og_image.png">







<link rel="icon" href="/images/favicon.svg">


<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/bulma@0.7.2/css/bulma.css">
<link rel="stylesheet" href="https://use.fontawesome.com/releases/v5.4.1/css/all.css">
<link rel="stylesheet" href="https://fonts.googleapis.com/css?family=Ubuntu:400,600|Source+Code+Pro">
<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/highlight.js@9.12.0/styles/atom-one-dark.css">


    
    
    
    <style>body>.footer,body>.navbar,body>.section{opacity:0}</style>
    

    
    
    
    <link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/lightgallery@1.6.8/dist/css/lightgallery.min.css">
    <link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/justifiedGallery@3.7.0/dist/css/justifiedGallery.min.css">
    

    
    

<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/outdatedbrowser@1.1.5/outdatedbrowser/outdatedbrowser.min.css">


    
    
    
    

<link rel="stylesheet" href="/css/back-to-top.css">


    
    

    
    
    
    

    
    
<link rel="stylesheet" href="/css/progressbar.css">
<script src="https://cdn.jsdelivr.net/npm/pace-js@1.0.2/pace.min.js"></script>

    
    
    


<link rel="stylesheet" href="/css/style.css">
</head>
<body class="is-1-column">
    <nav class="navbar navbar-main">
    <div class="container">
        <div class="navbar-brand is-flex-center">
            <a class="navbar-item navbar-logo" href="/">
            
                <img src="/images/logo.svg" alt="《大话数据结构》一" height="28">
            
            </a>
        </div>
        <div class="navbar-menu">
            
            <div class="navbar-start">
                
                <a class="navbar-item"
                href="/">首页</a>
                
                <a class="navbar-item"
                href="/archives">归档</a>
                
                <a class="navbar-item"
                href="/categories">分类</a>
                
                <a class="navbar-item"
                href="/tags">标签</a>
                
                <a class="navbar-item"
                href="/links">友链</a>
                
                <a class="navbar-item"
                href="/about">关于</a>
                
            </div>
            
            <div class="navbar-end">
                
                
                
                <a class="navbar-item search" title="搜索" href="javascript:;">
                    <i class="fas fa-search"></i>
                </a>
                
            </div>
        </div>
    </div>
</nav>
    
    <section class="section">
        <div class="container">
            <div class="columns">
                <div class="column is-12 has-order-2 column-main"><div class="card">
    
    <div class="card-content article ">
        
        <div class="level article-meta is-size-7 is-uppercase is-mobile is-overflow-x-auto">
            <div class="level-left">
                <time class="level-item has-text-grey" datetime="2019-03-05T15:41:00.000Z">2019-03-05</time>
                
                <div class="level-item">
                <a class="has-link-grey -link" href="/categories/《大话数据结构》/">《大话数据结构》</a>
                </div>
                
                
                <span class="level-item has-text-grey">
                    
                    
                    7 分钟 读完 (大约 1008 个字)
                </span>
                
                
            </div>
        </div>
        
        <h1 class="title is-size-3 is-size-4-mobile has-text-weight-normal">
            
                《大话数据结构》一
            
        </h1>
        <div class="content">
            <h1 id="第1章-数据结构绪论"><a href="#第1章-数据结构绪论" class="headerlink" title="第1章 数据结构绪论"></a>第1章 数据结构绪论</h1><a id="more"></a>
<ul>
<li>数据：是描述客观事物的符号，是计算机中可以操作的对象，是能被计算机识别，并输入给计算机处理的符号集合。</li>
<li>数据元素： 是组成数据的、有一定意义的基本单位，在计算机中通常作为整体处理。也被称为记录。</li>
<li>数据项：一个数据元素可以由若干个数据项组成。数据项是数据不可分割的最小单位。</li>
<li>数据对象：是性质相同的数据元素的集合，是数据的子集。</li>
<li>数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。</li>
</ul>
<h2 id="逻辑结构与物理结构"><a href="#逻辑结构与物理结构" class="headerlink" title="逻辑结构与物理结构"></a>逻辑结构与物理结构</h2><h4 id="1-逻辑结构：是指数据对象中数据元素之间的相互关系。分为以下4种："><a href="#1-逻辑结构：是指数据对象中数据元素之间的相互关系。分为以下4种：" class="headerlink" title="1. 逻辑结构：是指数据对象中数据元素之间的相互关系。分为以下4种："></a>1. 逻辑结构：是指数据对象中数据元素之间的相互关系。分为以下4种：</h4><ul>
<li>集合机构</li>
<li>线性结构</li>
<li>树形结构</li>
<li>图形结构</li>
</ul>
<h4 id="2-物理结构：是指数据的逻辑结构在计算机中的存储形式。"><a href="#2-物理结构：是指数据的逻辑结构在计算机中的存储形式。" class="headerlink" title="2. 物理结构：是指数据的逻辑结构在计算机中的存储形式。"></a>2. 物理结构：是指数据的逻辑结构在计算机中的存储形式。</h4><ul>
<li>顺序存储结构：是把数据元素放在地址连续的存储单元里，其数据间的逻辑关系和物理关系是一致的。</li>
<li>链式存储结构：是把数据元素存放在任意的存储单元里，这组单元可以是连续的，也可以是不连续的。</li>
</ul>
<h2 id="抽象数据类型"><a href="#抽象数据类型" class="headerlink" title="抽象数据类型"></a>抽象数据类型</h2><p>数据类型：是指一组性质相同的值得集合及定义在此集合上的一些操作的总称。<br>C语言中，按照取值的不同，可以分为两类：</p>
<ul>
<li>原子类型：是不可以再分解的基本类型，包括整型、实型、字符型等。</li>
<li>结构类型：由若干个类型组合而成，是可以再分解的。例如，整型数组是由若干整型数组组成的。</li>
</ul>
<p>抽象数据类型（Abstract Data Type, ADT）：是指一个数学模型及定义在该模型上的一组操作。</p>
<h1 id="第2章-算法"><a href="#第2章-算法" class="headerlink" title="第2章 算法"></a>第2章 算法</h1><p>算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有序序列，并且每条指令表示一个或多个操作。</p>
<h2 id="算法的特性"><a href="#算法的特性" class="headerlink" title="算法的特性"></a>算法的特性</h2><ol>
<li>输入输出</li>
<li>有穷性</li>
<li>确定性</li>
<li>可行性</li>
</ol>
<h2 id="算法设计的要求"><a href="#算法设计的要求" class="headerlink" title="算法设计的要求"></a>算法设计的要求</h2><ol>
<li>正确性</li>
<li>可读性</li>
<li>健壮性</li>
<li>时间效率高和存储量低</li>
</ol>
<h2 id="算法效率的度量方法"><a href="#算法效率的度量方法" class="headerlink" title="算法效率的度量方法"></a>算法效率的度量方法</h2><ol>
<li>事后统计方法（不科学、不准确）</li>
<li>事前分析估算方法</li>
</ol>
<h2 id="函数的渐近式增长"><a href="#函数的渐近式增长" class="headerlink" title="函数的渐近式增长"></a>函数的渐近式增长</h2><p>函数的渐近增长：给定两个函数 f(n) 和 g(n), 如果存在一个整数N，使得对于所有的 n &gt; N, f(n) 总是比 g(n) 大，那么，我们说 f(n) 的增长渐近快于 g(n)。</p>
<h2 id="算法时间复杂度"><a href="#算法时间复杂度" class="headerlink" title="算法时间复杂度"></a>算法时间复杂度</h2><p>在进行算法分析时，语句总的执行次数 T(n) 是关于问题规模 n 的函数，进而分析 T(n) 随 n 的变化情况并确定 T(n) 的数量级。算法的时间复杂度，也就是算法的时间度量，记作：T(n) = O(f(n))。它表示随问题规模 n 的增大，算法执行时间的增长率和 f(n) 的增长率相同，称作算法的渐近时间复杂度，简称为时间复杂度。其中 f(n) 是问题规模 n 的某个函数。</p>
<h2 id="推导大-O-阶方法"><a href="#推导大-O-阶方法" class="headerlink" title="推导大 O 阶方法"></a>推导大 O 阶方法</h2><ol>
<li>用常数 1 取代运行时间中的所有加法常数。</li>
<li>在修改后的运行次数函数中，只保留最高阶项。</li>
<li>如果最高阶存在且不是 1，则去除与这个项相乘的常数。<br>得到的结果就是大 O 阶。</li>
</ol>
<h2 id="常见的时间复杂度"><a href="#常见的时间复杂度" class="headerlink" title="常见的时间复杂度"></a>常见的时间复杂度</h2><p>O(1) &lt; O(logn) &lt; O(n) &lt; O(nlogn) &lt; O(n^2) &lt; O(n^3) &lt; O(2^n) &lt; O(n!) &lt; O(n^n)</p>

        </div>
        
        <div class="level is-size-7 is-uppercase">
            <div class="level-start">
                <div class="level-item">
                    <span class="is-size-6 has-text-grey has-mr-7">#</span>
                    <a class="has-link-grey -link" href="/tags/学习笔记/">学习笔记</a>
                </div>
            </div>
        </div>
        
        
        
    </div>
</div>





<div class="card card-transparent">
    <div class="level post-navigation is-flex-wrap is-mobile">
        
        <div class="level-start">
            <a class="level level-item has-link-grey  article-nav-prev" href="/DataStructurePart2/">
                <i class="level-item fas fa-chevron-left"></i>
                <span class="level-item">《大话数据结构》二</span>
            </a>
        </div>
        
        
        <div class="level-end">
            <a class="level level-item has-link-grey  article-nav-next" href="/CodingGuidelines/">
                <span class="level-item">iOS 代码规范</span>
                <i class="level-item fas fa-chevron-right"></i>
            </a>
        </div>
        
    </div>
</div>



<div class="card">
    <div class="card-content">
        <h3 class="title is-5 has-text-weight-normal">评论</h3>
        
<div id="comment-container"></div>
<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/gitalk@1.6.0/dist/gitalk.css">
<script src="https://cdn.jsdelivr.net/npm/gitalk@1.6.0/dist/gitalk.min.js"></script>

<script>
    var gitalk = new Gitalk({
        clientID: '7cf9ae5a9ae4228f59ef',
        clientSecret: 'a60824892847d86dab15dae00b18a8227f9af769',
        id: '04944582005d941a5edb4f2d6802f8b5',
        repo: 'Comments',
        owner: 'objcvip',
        admin: "objcvip",
        createIssueManually: false,
        distractionFreeMode: true
    })
    gitalk.render('comment-container')
</script>

    </div>
</div>
</div>
                
                
            </div>
        </div>
    </section>
    <footer class="footer">
    <div class="container">
        <div class="level">
            <div class="level-start has-text-centered-mobile">
                <a class="footer-logo is-block has-mb-6" href="/">
                
                    <img src="/images/logo.svg" alt="《大话数据结构》一" height="28">
                
                </a>
                <p class="is-size-7">
                &copy; 2020 ObjC.vip&nbsp;
                All rights reserved.
                
                </p>
            </div>
            <div class="level-end">
            
            </div>
        </div>
    </div>
</footer>
    <script src="https://cdn.jsdelivr.net/npm/jquery@3.3.1/dist/jquery.min.js"></script>
<script src="https://cdn.jsdelivr.net/npm/moment@2.22.2/min/moment-with-locales.min.js"></script>
<script>moment.locale("zh-CN");</script>

<script>
var IcarusThemeSettings = {
    article: {
        highlight: {
            clipboard: true,
            fold: 'unfolded'
        }
    }
};
</script>


    <script src="https://cdn.jsdelivr.net/npm/clipboard@2.0.4/dist/clipboard.min.js" defer></script>



    
    
    
    <script src="/js/animation.js"></script>
    

    
    
    
    <script src="https://cdn.jsdelivr.net/npm/lightgallery@1.6.8/dist/js/lightgallery.min.js" defer></script>
    <script src="https://cdn.jsdelivr.net/npm/justifiedGallery@3.7.0/dist/js/jquery.justifiedGallery.min.js" defer></script>
    <script src="/js/gallery.js" defer></script>
    

    
    

<div id="outdated">
    <h6>Your browser is out-of-date!</h6>
    <p>Update your browser to view this website correctly. <a id="btnUpdateBrowser" href="http://outdatedbrowser.com/">Update
            my browser now </a></p>
    <p class="last"><a href="#" id="btnCloseUpdateBrowser" title="Close">&times;</a></p>
</div>
<script src="https://cdn.jsdelivr.net/npm/outdatedbrowser@1.1.5/outdatedbrowser/outdatedbrowser.min.js" defer></script>
<script>
    document.addEventListener("DOMContentLoaded", function () {
        outdatedBrowser({
            bgColor: '#f25648',
            color: '#ffffff',
            lowerThan: 'flex'
        });
    });
</script>


    
    
<script src="https://cdn.jsdelivr.net/npm/mathjax@2.7.5/unpacked/MathJax.js?config=TeX-MML-AM_CHTML" defer></script>
<script>
document.addEventListener('DOMContentLoaded', function () {
    MathJax.Hub.Config({
        'HTML-CSS': {
            matchFontHeight: false
        },
        SVG: {
            matchFontHeight: false
        },
        CommonHTML: {
            matchFontHeight: false
        },
        tex2jax: {
            inlineMath: [
                ['$','$'],
                ['\\(','\\)']
            ]
        }
    });
});
</script>

    
    

<a id="back-to-top" title="回到顶端" href="javascript:;">
    <i class="fas fa-chevron-up"></i>
</a>
<script src="/js/back-to-top.js" defer></script>


    
    

    
    
    
    

    
    
    
    
    


<script src="/js/main.js" defer></script>

    
    <div class="searchbox ins-search">
    <div class="searchbox-container ins-search-container">
        <div class="searchbox-input-wrapper">
            <input type="text" class="searchbox-input ins-search-input" placeholder="想要查找什么..." />
            <span class="searchbox-close ins-close ins-selectable"><i class="fa fa-times-circle"></i></span>
        </div>
        <div class="searchbox-result-wrapper ins-section-wrapper">
            <div class="ins-section-container"></div>
        </div>
    </div>
</div>
<script>
    (function (window) {
        var INSIGHT_CONFIG = {
            TRANSLATION: {
                POSTS: '文章',
                PAGES: '页面',
                CATEGORIES: '分类',
                TAGS: '标签',
                UNTITLED: '(无标题)',
            },
            CONTENT_URL: '/content.json',
        };
        window.INSIGHT_CONFIG = INSIGHT_CONFIG;
    })(window);
</script>
<script src="/js/insight.js" defer></script>
<link rel="stylesheet" href="/css/search.css">
<link rel="stylesheet" href="/css/insight.css">
    
</body>
</html>